package com.captain.leetcode.回溯算法;

import java.util.*;

/**
 * @author captain
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],
 * [1,2,1],
 * [2,1,1]]
 * 示例 2：
 * <p>
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * @Date 2021/7/24 10:48
 */
public class 全排列II47 {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 2};
        new 全排列II47().permuteUnique(arr).forEach(System.out::println);
    }

    private Deque<Integer> path = new ArrayDeque<>();

    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        //记录使用过的数字
        int len = nums.length;
        int[] oldIndex = new int[len];
        //排序组合
        //排序 减枝叶的前提
        Arrays.sort(nums);
        dfs(nums, len, oldIndex);
        return res;
    }

    private void dfs(int[] nums, int len, int[] oldIndex) {
        //回溯条件
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        //[1,1,2]   [,,,]
        //遍历层级
        for (int i = 0; i < len; i++) {
            //过滤掉上一次的这个数字
            if (oldIndex[i] == 1) continue;
            //i > 0 && nums[i] == nums[i - 1] 考虑到行的情况
            //存在列的情况,nums[i] == nums[i - 1] 因为考虑行的情况, 所以
            // oldIndex[i - 1] == 0 表明只考虑行的过滤
            if (i > 0 && nums[i] == nums[i - 1] && oldIndex[i - 1] == 0) {
                continue;
            }
            //访问 = 1 没有访问 0
            oldIndex[i] = 1;
            path.add(nums[i]);
            dfs(nums, len, oldIndex);
            oldIndex[i] = 0;
            path.removeLast();
        }
    }
}
